1. Field of the Invention
The present invention relates to image coding of moving pictures.
2. Description of Prior Art
Recently, a mobile instrument such as mobile phone is widely used as a terminal unit for transmitting information, and it is possible to talk and send a moving picture to anyone whenever and wherever. Therefore it is desirable to run a mobile instrument for a long time with a limited cell capacity for driving the mobile instrument.
An MPEG (Motion Picture Experts Group) encoder is used in a mobile instrument to compress moving pictures. A motion compensator in an MPEG encoder estimates a motion between pictures for predictive coding. The position of a macroblock which matches best with a reference picture is detected in a current picture, and the picture at the position is used as a predictive picture. Then, the position is sent for encoding as motion vector information, and the picture data is encoded by using the motion vector to compensate the motion. Full search method is used as a block matching technique to determine the motion vector. In an MPEG encoder which uses the full search method, a motion compensator performs a large part of the computation. Therefore, it is necessary to provide a motion compensator of lower consumption power.
Full search method used for block matching is a technique which performs search in all cases. In this method, a value to be evaluated, for example, a sum of distortions in the block (a sum of square difference) on a macroblock (TB: a template block of 16*16 pixels) in a current picture is calculated on every macroblock in a search range (SW: search window) of a reference picture, and a macroblock having the minimum evaluated value is detected as motion vector (Vx, Vy). If the search range is ±16*±16, the computation is performed on vectors of 322 Because the computation is performed on all the vectors, the quality of the image obtained by full search method is very good, but the required computation power is very large.
Techniques such as greedy search method (for example, H. Nakayama et al., “An MPEG-4 Video LSI with an Error-Resilient Codec Core based on a Fast Motion Estimation Algorithm”, Proc. ISSCC 2002, 22-2, 2002) and gradient descent search method (for example, M. Takabayashi et al., “A Fast Motion Vector Detection based on Gradient Method”, Technical Report of IEICE, IE2001-74, September 2001) can decrease the computation power very much than that of the full search method. In greedy search method, an initial vector is calculated first wherein a vector having the smallest evaluated value of, for example, a sum of square difference among top, upper right and left vectors is selected as the initial vector. Next, block matching of four neighboring pixels is performed in the precision of a half-pel, and the macroblock is moved at the precision of half-pel in the direction of a minimum. This process is repeated, and it is stopped when the macroblock is moved to a position having the minimum value.
The gradient descent method is a kind of steepest descent method. Differential coefficients of an evaluated value are calculated at a search point, and the evaluated value is calculated in the direction of the steepest downward gradient derived from the differential coefficients. A vector having the minimum evaluated value is determined as a motion vector. In the calculation, an evaluated value of an initial motion vector is calculated. Next, the differential coefficients are calculated, and the evaluated value is calculated in the direction derived from the differential coefficients to determine the minimum in the one-dimensional search. In this method, the differential coefficients are calculated, and the evaluated value is calculated only in the direction derived from the differential coefficients in contrast to the above-mentioned full search method. Then, the required computation power is decreased in the gradient descent method.
Lower computation power and higher quality of image are desirable in the calculation of motion prediction. The above-mentioned gradient descent search method has a disadvantage that it is liable to lead to a local solution, depending very much on the initial value, and in such a case, the optimum motion vector cannot be detected, and image quality is deteriorated. Therefore, it is desirable that the computation power is decreased without deteriorating image quality.